//找到所有逆序对
public class ReversePairs {
}
class ReversePairsSolution {
    int ret = 0;
    public int reversePairs(int[] nums) {
        mergeSort(nums,0,nums.length-1);
        return ret;
    }
    void mergeSort(int[] nums,int l,int r){
        if(l<r){
            int m = (l+r)/2;
            mergeSort(nums,l,m);
            mergeSort(nums,m+1,r);
            merge(nums,l,m,r);
        }
    }
    void merge(int[] nums,int l,int m,int r){
        int li = l;
        int ri = m+1;
        int[] tmp = new int[r-l+1];
        int index = 0;
        while(li<=m&&ri<=r){
            if(nums[li]>nums[ri]){
                ret+=m-li+1;
                tmp[index++] = nums[ri++];
            }else{
                tmp[index++] = nums[li++];
            }
        }
        while(li<=m){
            tmp[index++] = nums[li++];
        }
        while(ri<=r){
            tmp[index++] = nums[ri++];
        }
        for(int i=l;i<=r;i++){
            nums[i] = tmp[i-l];
        }
    }
}